def count_edges(adjacency_matrix):
n = len(adjacency_matrix)
edge_count = 0
for i in range(n):
for j in range(i+1, n):
if adjacency_matrix[i][j] == 1:
edge_count += 1
return edge_count
# Ввод количества вершин и матрицы смежности
n = int(input("Введите количество вершин: "))
adjacency_matrix = []
for _ in range(n):
row = list(map(int, input().split()))
adjacency_matrix.append(row)
# Вычисление количества ребер и вывод результата
edge_count = count_edges(adjacency_matrix)
print("Количество ребер в графе:", edge_count)
В этой программе определена функция count_edges
, которая принимает матрицу смежности в качестве аргумента. Функция проходит по каждой паре вершин в графе и проверяет, есть ли между ними ребро (1 в матрице смежности). Если ребро есть, то увеличивается счетчик ребер. В конце функция возвращает количество ребер.
Программа сначала запрашивает количество вершин в графе, а затем построчно вводит матрицу смежности. После этого вычисляется количество ребер в графе с помощью функции count_edges
и выводится результат.
Например, при вводе следующей матрицы смежности для графа с 4 вершинами:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Программа выведет:
Количество ребер в графе: 4
То есть в данном графе 4 ребра.
Также пример программы
m = (map(int, input().split()) for _ in range(int(input('Num of nodes: '))))
a = {frozenset([ci+1, ni+1]) for ni, ne in enumerate(m) for ci, ce in enumerate(ne) if ce == 1}
print('Num of edges:', len(a))
Num of nodes: 6
1 1 0 0 1 0
1 0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 1 1
1 1 0 1 0 0
0 0 0 1 0 0
Num of edges: 8